import java.util.Arrays;
import java.util.Random;

public class SelectK {

    /**
     * 找到第k个数
     *
     * @param arr
     * @param k
     * @return
     */
    public int selectK(int[] arr, int k) {
        Random random = new Random();
        int kIndex = selectK(arr, 0, arr.length - 1, k, random);
        return arr[kIndex];
    }


    /**
     * 找到排序后第k个元素的索引
     *
     * @param arr
     * @param l
     * @param r
     * @param k
     * @param random
     * @return
     */
    private int selectK(int[] arr, int l, int r, int k, Random random) {
        int p = partition(arr, l, r, random);
        if (k == p) return p;
        if (k < p) return selectK(arr, l, p - 1, k, random);
        return selectK(arr, p + 1, r, k, random);
    }


    private int partition(int[] arr, int l, int r, Random random) {
        int p = random.nextInt(r - l + 1) + l;
        swap(arr, l, p);
        //arr[l+1...j-1]<=v;arr[j+1..r]>=v
        int i = l + 1, j = r;
        while (true) {
            while (i <= j && arr[i] < arr[l]) i++;
            while (i <= j && arr[j] > arr[l]) j--;
            if (i >= j) break;
            swap(arr, i, j);
            i++;
            j--;
        }
        swap(arr, l, j);
        return j;
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public void printArr(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i]);
            if (i < nums.length - 1) {
                System.out.print(",");
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {5, 4,2,3,5};
        SelectK selectK = new SelectK();
        System.out.println("selectK.selectK(arr,2) = " + selectK.selectK(arr, 2));
    }
}
